
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
    if(lists.length === 0) return null;
    // let first: ListNode | null = lists[0];
    // for (let i = 1; i < lists.length; i++) {
    //     first = mergeTwoLists(first, lists[i]);
    // }
    // return first;
    // 使用分治策略合并链表
    return mergeLists(lists, 0, lists.length - 1);
};
function mergeLists(lists: Array<ListNode | null>, left: number, right: number): ListNode | null {
    // 基准情况：只有一个链表
    if (left === right) {
        return lists[left];
    }

    // 基准情况：两个链表，直接合并
    if (left + 1 === right) {
        return mergeTwoLists(lists[left], lists[right]);
    }

    // 分治：递归合并左右两部分
    const mid = Math.floor((left + right) / 2);
    const leftMerged = mergeLists(lists, left, mid);
    const rightMerged = mergeLists(lists, mid + 1, right);

    return mergeTwoLists(leftMerged, rightMerged);
}
function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    // 创建哑节点作为新链表的起始点
    const dummy = new ListNode(-1);
    let current = dummy;

    // 当两个链表都不为空时，比较节点值
    while (list1 && list2) {
        if (list1.val <= list2.val) {
            current.next = list1;
            list1 = list1.next;
        } else {
            current.next = list2;
            list2 = list2.next;
        }
        current = current.next;
    }

    // 将剩余的链表直接接上
    current.next = list1 ?? list2;

    return dummy.next;
};